package 单周赛.history;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 *
 */
public class 第359场单周赛 {

    public static void main(String[] args) {

    }

    public boolean isAcronym(List<String> words, String s) {
        if (words.size() != s.length()) {
            return false;
        }
        for (int i = 0; i < words.size(); i++) {
            if (words.get(i).charAt(0) != s.charAt(i)) {
                return false;
            }
        }

        return true;
    }

    /**
     * 贪心+双指针列表模拟
     * 某一对和 = k ，取较小的值
     * 双指针判断存在 = k 的对
     */
    public int minimumSum(int n, int k) {
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            list.add(i);
        }
        int next = n + 1;
        boolean flag = true;
        while (flag) {
            flag = false;
            int left = 0, right = n - 1;
            while (left < right) {
                int sum = list.get(left) + list.get(right);
                if (sum == k) {
                    list.remove(right);
                    list.add(next);
                    next++;
                    flag = true;
                } else if (sum > k) {
                    right--;
                } else {
                    left++;
                }
            }
        }

        int sum = 0;
        for (Integer num : list) {
            sum += num;
        }
        return sum;
    }

    /**
     * 贪心+哈希表
     * 如果哈希表中存在 k - i 的数，那么 i 不能取
     */
    public int minimumSum2(int n, int k) {
        int ans = 0;
        Set<Integer> set = new HashSet<>();
        int curNum = 1;
        while (set.size() < n) {
            if (!set.contains(k - curNum)) {
                ans += curNum;
                set.add(curNum);
            }
            curNum++;
        }
        return ans;
    }

}
